package 奶牛排队;

import java.util.Scanner;

public class Main {
    static int N = 50010, M = 20;
    static int[][] f = new int[N][M];
    static int[][] g = new int[N][M];
    static int[] log = new int[N];
    static int[] h = new int[N];

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int q = in.nextInt();
        for (int i = 1; i <= n; i++) {
            h[i] = in.nextInt();
        }
        //查询
        for (int i = 1; i <= n; i++) {
            while (1 << (log[i] + 1) <= i) {
                log[i]++;
            }
        }
        //创建
        for (int j = 0; 1 << j <= n; j++) {
            for (int i = 1; i + (1 << j) - 1 <= n; i++) {
                if (j == 0) {
                    f[i][j] = g[i][j] = h[i];
                } else {
                    f[i][j] = Math.max(f[i][j - 1], f[i + (1 << j - 1)][j - 1]);
                    g[i][j] = Math.min(g[i][j - 1], g[i + (1 << j - 1)][j - 1]);
                }
            }
        }
        while (q-- > 0) {
            int l = in.nextInt();
            int r = in.nextInt();
            int t = log[r - l + 1];
            int maxval = Math.max(f[l][t], f[r - (1 << t) + 1][t]);
            int minval = Math.min(g[l][t], g[r - (1 << t) + 1][t]);
            System.out.println(maxval - minval);
        }
    }
}
